package class07;

/**
 * 预测赢家【LeetCode486】
 */
public class Code03_CardsInLine {

	/**
	 * 暴力递归尝试
	 * @param arr
	 * @return
	 */
	public static int win1(int[] arr) {
		if (arr == null || arr.length == 0) {
			return 0;
		}
		return Math.max(f(arr, 0, arr.length - 1), s(arr, 0, arr.length - 1));
	}

	/*
	* 先手函数
	* 当前该你拿arr[i...j] i和j表示左右边界
	* 返回最好的分数
	* */
	public static int f(int[] arr, int i, int j) {
		if (i == j) {
			return arr[i];
		}
		return Math.max(arr[i] + s(arr, i + 1, j), arr[j] + s(arr, i, j - 1));
	}

	/*
	* 后手函数
	* 当前不该你拿，是对方在arr[i..j]范围上拿
	* 返回你的最好分数
	* */
	public static int s(int[] arr, int i, int j) {
		if (i == j) {
			return 0;
		}
		return Math.min(f(arr, i + 1, j), f(arr, i, j - 1));
	}




	/**
	 * 记忆化搜索
	 * @param arr
	 * @return
	 */
	public static int winByMS(int[] arr) {
		if (arr == null || arr.length == 0) {
			return 0;
		}

		// 加缓存
		// 可变参数 左右边界的位置 i 和 j
		int[][] dpf = new int[arr.length][arr.length];
		int[][] dps = new int[arr.length][arr.length];
		// 初始化，因为拿到的是最好的分数，所以初始化为-1
		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr.length; j++) {
				dpf[i][j] = -1;
				dps[i][j] = -1;
			}
		}

		return Math.max(f1(arr, 0, arr.length - 1, dpf, dps), s1(arr, 0, arr.length - 1, dps, dpf));
	}

	/*
	 * 先手函数
	 * 当前该你拿arr[i...j] i和j表示左右边界
	 * 返回最好的分数
	 * 前一个二维数组表示作为先手的缓存
	 * 后一个二维数组表示作为后手的缓存
	 * */
	public static int f1(int[] arr, int i, int j, int[][] dpf, int[][] dps) {
		// 缓存命中，直接返回答案
		if (dpf[i][j] != -1) {
			return dpf[i][j];
		}

		// base case
		if (i == j) {
			dpf[i][j] = arr[i];
//			return dpf[i][j];
		} else {

			dpf[i][j] = Math.max(arr[i] + s1(arr, i + 1, j, dps, dpf), arr[j] + s1(arr, i, j - 1, dps, dpf));
		}


		return dpf[i][j];
	}

	/*
	 * 后手函数
	 * 当前不该你拿，是对方在arr[i..j]范围上拿
	 * 返回你的最好分数
 	 * 前一个二维数组表示作为先手的缓存
	 * 后一个二维数组表示作为后手的缓存
	 * */
	public static int s1(int[] arr, int i, int j, int[][] dps, int[][] dpf) {

		// 缓存命中
		if(dps[i][j] != -1) {
			return dps[i][j];
		}

		// 缓存未命中
		if (i == j) {
			dps[i][j] = 0;
//			return dps[i][j];
		} else {  //！！！ 这里一定要加else，因为i==j和 i!=j 是两个逻辑，不加else的话dp的值会被覆盖
			dps[i][j] = Math.min(f1(arr, i + 1, j, dpf, dps), f1(arr, i, j - 1, dpf, dps));
		}


		return dps[i][j];
	}




	/**
	 * 严格表结构DP
	 * @param arr
	 * @return
	 */
	public static int win2(int[] arr) {
		if (arr == null || arr.length == 0) {
			return 0;
		}
		int[][] f = new int[arr.length][arr.length];
		int[][] s = new int[arr.length][arr.length];
		for (int j = 0; j < arr.length; j++) {
			// f函数对角线值是arr[i]
			f[j][j] = arr[j];
			for (int i = j - 1; i >= 0; i--) {
				f[i][j] = Math.max(arr[i] + s[i + 1][j], arr[j] + s[i][j - 1]);
				s[i][j] = Math.min(f[i + 1][j], f[i][j - 1]);
			}
		}
		return Math.max(f[0][arr.length - 1], s[0][arr.length - 1]);
	}







	// for test
	public static void main(String[] args) {
		int[] arr = { 1, 9, 1 };
		System.out.println(win1(arr));
		System.out.println(winByMS(arr));
		System.out.println(win2(arr));

	}

}
